/*
https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-by-leetcode-solution/
 */
import java.util.HashMap;
import java.util.Map;

public class Solution466 {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        if (n1==0){
            return 0;
        }
        int s1Num=0,index=0,s2Num=0;
        Map<Integer,int[]> map=new HashMap<>();
        int[] pre;
        int[] now;
        while (true){
            s1Num++;
            for (int i=0;i<s1.length();i++) {
                char ch=s1.charAt(i);
                if (ch==s2.charAt(index)){
                    index++;
                    if (index==s2.length()) {
                        s2Num++;
                        index=0;
                    }
                }
            }
            if (s1Num==n1){
                return s2Num/n2;
            }
            if (map.containsKey(index)){
                int[] value=map.get(index);
                pre=new int[]{value[0],value[1]};
                now=new int[]{s1Num-value[0],s2Num-value[1]};
                break;
            }else{
                map.put(index,new int[]{s1Num,s2Num});
            }
        }
        int ans=pre[1]+(n1-pre[0])/now[0]*now[1];
        int rest=(n1-pre[0])%now[0];
        for (int i=0;i<rest;i++) {
            for (int j=0;j<s1.length();j++){
                char ch=s1.charAt(j);
                if (ch==s2.charAt(index)) {
                    index++;
                    if (index==s2.length()) {
                        ans++;
                        index=0;
                    }
                }
            }
        }
        return ans/n2;
    }

    public static void main(String[] args) {
        System.out.println(new Solution466().getMaxRepetitions("acb",4,"ab",2));
    }
}
